/**
 * Phan tich thua so nguyen to
 * @author TrinhNX
 *	Bai nay don gian voi so nho
 *	 Hoi xua lam theo lap (tu 1 -> n/2)
 *	 Nhung o day vo phai input lon qua, chac la BigInteger :D hoac Long :3
 *		Doc thi thay thuat toan RHO
 *		http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_RHO
 */
public class Euler003 {
	public static void main(String[] args) {
		// Dung RHO voi thuat toan chua thay doi
		// ham ngau nhien 1 + x * x
		final long input = 600851475143L;
		Euler003 main = new Euler003();
		long divisor;
		// Assign first
		divisor = main.rho(input);
		while (divisor != 1) {
			divisor = main.rho(input / divisor);
			System.out.println(divisor);
		}
	}

	// Random function x^2 + 1
	private long f(long x) {
		return x * x + 1;
	}

	// Uoc so chung lon nhat cua 2 so
	private long gcd(long x, long y) {
		if (y == 0) {
			return x;
		} else {
			return gcd(y, x % y);
		}
	}

	// Kiem tra co phai la so nguyen to
	private boolean isPrime(final long N) {
		for (long i = 2; i < (N / 2); i++) {
			if (N % i == 0)
				return false;
		}
		return true;
	}

	// Thuat toan RHO -> Dech biet :(
	private long rho(final long N) {
		long x1 = 2, x2 = 2, divisor;
		if (N % 2 == 0) {
			return 2;
		}
		do {
			x1 = f(x1) % N;
			x2 = f(f(x2)) % N;
			divisor = gcd(Math.abs(x1 - x2), N);
		} while (divisor == 1);
		return divisor;
	}

	// Get all
	private void factor(final long N) {
		if (N == 1) {
			System.out.println(N);
			return;
		}

		if (isPrime(N)) {
			System.out.println(N);
			return;
		}
		long divisor = rho(N);
		System.out.println("RHO: " + rho(N / divisor));
		factor(divisor);
		factor(N / divisor);
	}
}
